package alogrithm.list;

public class LinkList <T> {
	public LinkNode<T> head;
	public LinkNode<T> tail;
	
	public LinkList(){
		head=tail=null;
	}
	public int index=0;
	
	public LinkNode<T> add(T data){
		LinkNode<T> node=new LinkNode<T>(index++,data);
		node.next=head;
		head=node;
		return node;
	}
	
	public void display(){
		LinkNode<T> node=head;
		while(node!=null){
			System.out.printf("%3s-->", node.data);
			node=node.next;
		}
	}
	
	
	public void reverseDisplay(){
		System.out.println(tail);
		LinkNode<T> node=tail;
		while(node!=null){
			System.out.printf("%3s<--\n", node.data);
			node=node.pre;
		}
	}
	
	public boolean hasCycle(){
		boolean hasCycle=false;
		LinkNode<T> slow=head;
		LinkNode<T> fast=head;
		
		while(fast!=null && fast.next!=null){
			slow=slow.next;
			fast=fast.next.next;
			if(slow==fast){
				break;
			}
		}
		
		hasCycle=!(fast==null || fast.next==null);
		return hasCycle;
	}
	
	
	/**
	 * 判断链表是否相交
	 * 思路：
	 * 如果链表相交，则可定有公共的节点，假设2个链表为无环单向链表
	 * 则2个链表的最后一个节点必然相交，可以先遍历第一个链表然后记录最后一个节点
	 * 遍历第二个链表到最后一个节点和第一个链表的最后一个节点比较，如果相同，则相交
	 * 
	 * @param b
	 * @return
	 */
	public boolean isUnion(LinkList<T> b){
		boolean isUnion=false;
		LinkNode<T> firstLastNode=this.head;
		LinkNode<T> t=head;
		while(t!=null){
			firstLastNode=t;
			t=t.next;
		}
		
		LinkNode<T> s=null;
		LinkNode<T> l=b.head;
		while(l!=null){
			s=l;
			l=l.next;
		}
		
		if(firstLastNode.equals(s)){
			isUnion=true;
		}
		return isUnion;
	}
	
	
	/**
	 * 思路一：
	 * 遍历链表1，获取长度lenA
	 * 遍历链表2，获取长度lenB
	 * 如果lenA-lenB>0,则先遍历链表1到(lenA-lenB)长度，反之亦然
	 * 
	 * 同时遍历链表1和链表2，如果发现有相同的节点就跳出循环，即为第一个相交节点
	 * 
	 * @param b
	 * @return
	 */
	public LinkNode<T> getUnionFirstNode(LinkList<T> b){
		LinkNode<T> first=null;
		LinkNode<T> t=head;
		
		int thisLen=0;
		int thatLen=0;
		
		while(t!=null){
			t=t.next;
			thisLen++;
		}
		
		LinkNode<T> l=b.head;
		while(l!=null){
			l=l.next;
			thatLen++;
		}
		
		if(thisLen>thatLen){
			int gap=thisLen-thatLen;
			int i=0;
			while(i<gap){
				head=head.next;
				i++;
			}
		}else{
			int gap=thatLen-thisLen;
			int i=0;
			while(i<gap){
				b.head=b.head.next;
				i++;
			}
		}
		
		while(this.head!=null && b.head!=null){
			if(this.head.equals(b.head)){
				first=this.head;
				break;
			}
			
			this.head=this.head.next;
			b.head=b.head.next;
		}
		
		return first;
	}
	
	public LinkList<T> getUnionLinkList(LinkList<T> b){
		LinkList<T> result=new LinkList<T>();
		LinkNode<T> t=head;
		
		int thisLen=0;
		int thatLen=0;
		
		while(t!=null){
			t=t.next;
			thisLen++;
		}
		
		LinkNode<T> l=b.head;
		while(l!=null){
			l=l.next;
			thatLen++;
		}
		
		if(thisLen>thatLen){
			int gap=thisLen-thatLen;
			int i=0;
			while(i<gap){
				head=head.next;
				i++;
			}
		}else{
			int gap=thatLen-thisLen;
			int i=0;
			while(i<gap){
				b.head=b.head.next;
				i++;
			}
		}
		
		while(this.head!=null && b.head!=null){
			if(this.head.equals(b.head)){
				result.add(this.head.data);
			}
			
			this.head=this.head.next;
			b.head=b.head.next;
		}
		
		return result;
	}
	
	
	public LinkNode<T> findFirstLoopNode(){
		LinkNode<T> slow=head;
		LinkNode<T> fast=head;
		
		while(fast!=null && fast.next!=null){
			slow=slow.next;
			fast=fast.next.next;
			
			if(slow==fast){
				break;
			}
		}
		
		if(fast==null || fast.next==null){
			return null;
		}
		
		slow=head;
		while(slow!=fast){
			slow=slow.next;
			fast=fast.next;
		}
		
		return slow;
	}
	
	public int getCycleLength(){
		int length=0;
		LinkNode<T> slow=head;
		LinkNode<T> fast=head;
		while(fast!=null && fast.next!=null){
			slow=slow.next;
			fast=fast.next.next;
			
			length++;
			if(slow==fast){
				break;
			}
		}
		return length;
	}
	
	public static void main(String[] args) {
		LinkList<Integer> list=new LinkList<Integer>();
		LinkNode<Integer> l1=list.add(10);
		LinkNode<Integer> l3=list.add(234);
		list.add(4);
		LinkNode<Integer> ll=list.add(100);
		list.add(300);
		
		l1.next=ll;
		
		//list.display();
		boolean hasCycle=list.hasCycle();
		System.out.println("判断list是否有环");
		System.out.println(hasCycle);
		
		LinkList<Integer> b=new LinkList<Integer>();
		b.add(10);
		b.add(234);
		b.add(1);
		b.add(234);
//		System.out.println("判断链表是否相交");
//		System.out.println(list.isUnion(b));
//		System.out.println("获取2个相交链表的第一个相交节点");
//		System.out.println(list.getUnionFirstNode(b));
//		
//		System.out.println("获取2个链表的公共链表");
//		LinkList<Integer> result=list.getUnionLinkList(b);
		//result.display();
		
		System.out.println("获取环的第一个入口节点");
		System.out.println(list.findFirstLoopNode());
		
		System.out.println("环的长度为");
		System.out.println(list.getCycleLength());
	}
}
